package com.tgy.algorithm._经典题目01;

import com.tgy.algorithm.base.other.BiTreeNode;

import java.util.*;

public class _023_根据给出的先序和中序生成后序数组 {

    public static BiTreeNode generalBiTreeNode() {

        /**
         *               4
         *           2        3
         *        0     5  6     7
         */
        BiTreeNode root = new BiTreeNode(4);
        root.left = new BiTreeNode(2);
        root.right = new BiTreeNode(3);
        root.left.left = new BiTreeNode(0);
//        root.left.right = new BiTreeNode(5);
//        root.right.left = new BiTreeNode(6);
//        root.right.right = new BiTreeNode(7);
        return root;
    }

    public static int[] preOrder(BiTreeNode root) {

        if (root == null) {
            return null;
        }

        Stack<BiTreeNode> stack = new Stack<>();
        stack.push(root);
        LinkedList<Integer> container = new LinkedList<>();
        while (!stack.isEmpty()) {
            BiTreeNode node = stack.pop();
            container.add(node.value);
            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }
        int len = container.size();
        int[] rets = new int[len];
        for (int i = 0; i < len; i++) {
            rets[i] = container.get(i);
        }

        return rets;
    }

    public static int[] inOrder(BiTreeNode root) {
        if (root == null) {
            return null;
        }

        Stack<BiTreeNode> stack = new Stack<>();
        BiTreeNode node = root;
        List<Integer> container = new ArrayList<>();
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                container.add(node.value);
                node = node.right;
            }
        }

        int len = container.size();
        int[] rets = new int[len];
        for (int i = 0; i < len; i++) {
            rets[i] = container.get(i);
        }

        return rets;
    }

    public static int[] preInOrderToPostOrder(int[] preOrders,int[] inOrders) {

        if (preOrders == null || inOrders == null
                || preOrders.length != inOrders.length) {
            return null;
        }

        int len = preOrders.length;

        // 提前缓存位置信息
        HashMap<Integer, Integer> locations = new HashMap<>();
        for (int i = 0; i < inOrders.length; i++) {
            locations.put(inOrders[i],i);
        }

        int[] postOrders = new int[len];
        int postLoc = len - 1;
//        postLoc = len - 1;
        globalPostLoc = len  -1;
//        buildPostOrder(preOrders,0,len - 1,
//                       inOrders,0,len - 1,
//                       postOrders,postLoc,
//                        locations);
        buildPostOrder01(preOrders,0,len - 1,
                    inOrders,0,len - 1,
                    postOrders,0, len - 1,
                    locations
                );
        return postOrders;
    }

    public static int globalPostLoc;

    public static void buildPostOrder( int[] preOrders,int preLeft,int preRight,
                                       int[] inOrders, int inLeft, int inRight,
                                       int[] postOrders, int postLoc,
                                       Map<Integer,Integer> locations) {

        postOrders[globalPostLoc--] = preOrders[preLeft];
        if (preLeft >= preRight) {
            return;
        }

        int inLoc = locations.get(preOrders[preLeft]);
        // 3
        int leftLen = inLoc - inLeft;
        // 3
        int rightLen = inRight - inLoc;

        //
        buildPostOrder(preOrders,preLeft + leftLen + 1,preRight,
                inOrders,inLoc+1,inRight,
                postOrders,postLoc-1,
                locations
        );

        buildPostOrder(preOrders,preLeft+1,preLeft+leftLen,
                inOrders,inLeft,inLoc - 1,
                postOrders,
                postLoc - 2,
                locations
        );
    }

    public static void buildPostOrder01( int[] preOrders,int preLeft,int preRight,
                                       int[] inOrders, int inLeft, int inRight,
                                       int[] postOrders, int postLeft,int postRight,
                                       Map<Integer,Integer> locations) {

        postOrders[postRight] = preOrders[preLeft];
        if (preLeft >= preRight) {
            return;
        }

        int inLoc = locations.get(preOrders[preLeft]);
        // 3
        int leftLen = inLoc - inLeft;
        // 3
        int rightLen = inRight - inLoc;

        //
        buildPostOrder01(preOrders,preLeft + leftLen + 1,preRight,
                inOrders,inLoc+1,inRight,
                postOrders,postRight - rightLen,postRight - 1,
                locations
        );

        buildPostOrder01(preOrders,preLeft+1,preLeft+leftLen,
                inOrders,inLeft,inLoc - 1,
                postOrders, postLeft,postLeft + leftLen - 1,
                locations
        );
    }


    public static void main(String[] args) {
        BiTreeNode root = generalBiTreeNode();
        int[] preOrders = preOrder(root);
        int[] inOrders = inOrder(root);
        System.out.println(Arrays.toString(preOrders));
        System.out.println(Arrays.toString(inOrders));
        int[] postOrder = preInOrderToPostOrder(preOrders, inOrders);
        System.out.println(Arrays.toString(postOrder));
    }
}
